#include <iostream>
#include <vector>
#include <tuple>
#include <map>
#include <algorithm>
using namespace std;

//Definition for a binary tree node.
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr)
	{
	}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr)
	{
	}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right)
	{
	}
};

class Solution {
        int ans = 0;
        int path_sum(TreeNode *root, int targetsum, long sum, map<long, int> &presum)
        {
                if(root == nullptr){
                        return 0;
                }
                sum += root->val;
                ans += presum[sum - targetsum];
                presum[sum]++;
                path_sum(root->left, targetsum, sum, presum);
                path_sum(root->right, targetsum, sum, presum);
                presum[sum]--;
                return 0;
        }
    public:
	int pathSum(TreeNode *root, int targetSum)
	{
                ans = 0;
                map<long, int> presum;
                presum[0] = 1;
                path_sum(root, targetSum, 0, presum);
                return ans;
	}
};

int main()
{
	return 0;
}